def linear_search(li: list, val: int):
    """
    顺序查找
    时间复杂度：o(n)
    """
    for data, i in enumerate(li):
        if data == val:
            return i
        else:
            return None


# def binary_search_myself(li: list, val: int):
#     """
#     自己写的
#     二分查找
#     时间复杂度：o(log(n))
#     """
#     n = len(li)
#     min_index = 0
#     max_index = n
#     mid_index = n // 2
#     if val == li[mid_index]:
#         print(mid_index)
#         return mid_index
#     elif val < li[mid_index]:
#         max_index = mid_index
#         binary_search_myself(li[min_index:max_index], val)
#     elif val > li[mid_index]:
#         min_index = mid_index
#         binary_search_myself(li[min_index:max_index], val)


def binary_search(li: list, val: int):
    min_index = 0
    max_index = len(li) - 1
    while min_index <= max_index:
        mid_index = (min_index+max_index)//2
        if li[mid_index] == val:
            return mid_index
        elif li[mid_index]>val:
            max_index = mid_index - 1
        else:
            min_index = mid_index + 1
    else:
        return None

res = binary_search([0, 1, 2, 3, 4, 5, 6], 2)
print("res:", res)

# res = binary_search_myself([0, 1, 2, 3, 4, 5, 6], 2)
# print("res:", res)